import java.util.Scanner;

/**
 * @author yu
 * @date 2025年04月28日 22:50
 * @Description: 122. 买卖股票的最佳时机 II
 * 给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
 * 你可以买卖多次
 * 返回 你能获得的 最大 利润 。
 */
public class _09_dp_25_122maxProfit {
    /*2.动态规划*/
    public static int maxProfit3(int[] prices) {
        if (prices == null || prices.length == 0) return 0;
        int length = prices.length;
        // dp[i][0]代表第i天持有股票的最大收益
        // dp[i][1]代表第i天不持有股票的最大收益
        int[][] dp = new int[length][2];
        int result = 0;
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        for (int i = 1; i < length; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
            dp[i][1] = Math.max(dp[i - 1][0] + prices[i], dp[i - 1][1]);
        }
        return dp[length - 1][1];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入股票价格，以空格分隔：");
        String input = sc.nextLine();
        String[] priceStrs = input.split(" ");
        int[] prices = new int[priceStrs.length];
        for (int i = 0; i < priceStrs.length; i++) {
            prices[i] = Integer.parseInt(priceStrs[i]);
        }
//        _09_dp_24_122maxProfit solution = new _09_dp_24_122maxProfit();
//        int profit1 = solution.maxProfit1(prices);
        int profit3 = maxProfit3(prices);
//        System.out.println("使用贪心算法得到的最大利润: " + profit1);
        System.out.println("使用动态规划算法得到的最大利润: " + profit3);
        sc.close();
    }
}
